package com.hardy.backtracking;

import java.util.ArrayList;

/**
 * User: Ruijie Date: 2016/9/23
 */
public class SubSetsProblem {

    public static ArrayList<ArrayList<Integer>> subsets(int[] arr){
        ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> arrayList=new ArrayList<Integer>();
        dfs(0,arr,res,arrayList);
        return res;
    }

    private static void dfs(int n,int[] arr, ArrayList<ArrayList<Integer>> res,ArrayList<Integer> arrayList) {
        if(n>=arr.length){
            res.add(new ArrayList<>(arrayList));
        }else{
            //不选择第n个元素
            dfs(n+1,arr,res,arrayList);
            arrayList.add(arr[n]);
            dfs(n+1,arr,res,arrayList);
            arrayList.remove(arrayList.size()-1);
        }
    }

    public static ArrayList<ArrayList<Integer>> _subsets(int[] arr){
        ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> arrayList=new ArrayList<Integer>();
        _dfs(0,arr,res,arrayList);
        return res;
    }

    private static void _dfs(int start, int[] arr, ArrayList<ArrayList<Integer>> res,
                             ArrayList<Integer> arrayList) {
        res.add(new ArrayList<>(arrayList));
        for(int i=start;i<arr.length;i++){
            arrayList.add(arr[i]);
            _dfs(i+1,arr,res,arrayList);
            arrayList.remove(arrayList.size()-1);
        }
    }

    public static void main(String[] args) {
        int[] a={1,2,3};
        System.out.println(subsets(a));
        System.out.println(_subsets(a));
    }

}
